package zeng.glogo.learn;

import java.util.ArrayList;
import java.util.Scanner;

public class BinaryTree1 {
	
	Node root = new Node();	//��ڵ�
	int nodeCount = 0;
	static ArrayList<Node> array = new ArrayList<Node>();
	
	public static int getDepth(Node root){
		int depthLeft=0;
		int depthRight=0;
		int depth=0;
		
		if(root.left>0)
			depthLeft=getDepth(root.leftNode)+1;
		if(root.right>0)
			depthRight=getDepth(root.rightNode)+1;
		if(depthLeft>=depthRight)
			depth=depthLeft;
		else
			depth=depthRight;
		return depth;
	}
	
	public static void main(String[] args) {
		BinaryTree1 tree = new BinaryTree1();
		//Scanner scanner = new Scanner("8 2 3 4 -1 5 6 -1 -1 7 8 -1 -1 -1 -1 -1 -1");
		Scanner scanner = new  Scanner(System.in);
		tree.nodeCount = scanner.nextInt();
		int a = scanner.nextInt();
		int b = scanner.nextInt();
		int temp = 1;
		tree.root.setNodeValue(temp);	//������Ϊ1
		tree.root.setLeft(a);
		tree.root.setRight(b);
		array.add(0,tree.root);
		while(temp < tree.nodeCount){
			a = scanner.nextInt();
			b = scanner.nextInt();
			Node node = tree.new Node();
			node.setLeft(a);	//����-1
			node.setRight(b);	//����-1
			node.setNodeValue(++temp);
			array.add(node.getNodeValue()-1,node);
		}
				
		for(int i = 0;i<array.size(); i++){
			Node node = array.get(i);		//��һ���Ǹ���
			if(node.getLeft()>=0)
			{
				Node nodeLeft = array.get(node.getLeft()-1);
				node.leftNode=nodeLeft;
			}
			if(node.getRight()>=0)
			{
				Node nodeRight = array.get(node.getRight()-1);
				node.rightNode=nodeRight;
			}
		}
		for(int i=array.size()-1;i>= 0;i--)
		{
			System.out.println(array.get(i).nodeValue);
		}
		int depth=getDepth(array.get(0))+1;
		System.out.print("depth="+depth);
		
		scanner.close();
	}
	
	//�ڲ��࣬��װ�����Ϣ
	class Node{
		
		private int nodeValue;		//�����
		private Node leftNode;
		private Node rightNode;
		private int left;			//����
		private int right;			//�ҽ��
		protected int getLeft() {
			return left;
		}
		protected void setLeft(int left) {
			this.left = left;
		}
		protected int getRight() {
			return right;
		}
		protected void setRight(int right) {
			this.right = right;
		}
		protected int getNodeValue() {
			return nodeValue;
		}
		protected void setNodeValue(int nodeValue) {
			this.nodeValue = nodeValue;
		}
		protected Node getLeftNode() {
			return leftNode;
		}
		protected void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}
		protected Node getRightNode() {
			return rightNode;
		}
		protected void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}
	};
}
